package org.usmile.algorithms.leetcode.hard;

import java.util.ArrayList;
import java.util.List;

/**
 * 51. N 皇后
 *
 * 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
 * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 *
 * 示例 1：
 * 输入：n = 4
 * 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 * 解释：如上图所示，4 皇后问题存在两个不同的解法。
 *
 * 示例 2：
 * 输入：n = 1
 * 输出：[["Q"]]
 *
 * 提示：
 * 1 <= n <= 9
 */
public class _0051 {
}

class _0051_Solution {
    private List<List<String>> result;
    private int n;

    private int[] rows;
    private int[] cols;
    private int[] mains;
    private int[] secondary;


    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        this.rows = new int[n];
        this.cols = new int[n];
        this.mains = new int[2 * n - 1];
        this.secondary = new int[2 * n - 1];

        result = new ArrayList<>();

        dfs(0);

        return result;
    }

    private void dfs(int row) {
        if (row >= n) {
            return;
        }

        for (int col = 0; col < n; col++) {
            if (isNotUnderAttack(row, col)) {
                placeQueen(row, col);

                if (row == n - 1) {
                    addSolution();
                }

                dfs(row + 1);

                removeQueen(row, col);
            }
        }
    }

    private void addSolution() {
        List<String> solution = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
            int col = rows[i];
            String sb = ".".repeat(Math.max(0, col)) +
                    "Q" +
                    ".".repeat(Math.max(0, n - col - 1));
            solution.add(sb);
        }
        result.add(solution);
    }

    private void removeQueen(int row, int col) {
        rows[row] = 0;
        cols[col] = 0;
        mains[row - col + n - 1] = 0;
        secondary[row + col] = 0;
    }

    private void placeQueen(int row, int col) {
        rows[row] = col;
        cols[col] = 1;
        mains[row - col + n - 1] = 1;
        secondary[row + col] = 1;
    }

    private boolean isNotUnderAttack(int row, int col) {
        return cols[col] + mains[row - col + n - 1] + secondary[row + col] == 0;
    }
}